#include <iostream>
#include <algorithm> 
#include <assert.h>
using namespace std; 

namespace csd
{
    template<class T>
        class vector 
        {
        public:
            typedef T* iterator;
            typedef const T* const_iterator;
            
            iterator begin()
            {
                return _start;
            }
            
            iterator end()
            {
                return _finish;
            }

            const_iterator begin()const 
            {
                return _start;
            }

            const_iterator end()const 
            {
                return _finish;
            }

            vector()
                :_start(NULL)
                ,_finish(NULL)
                ,_end_of_storage(NULL)
            {
            }

            template <class InputIterator>
            vector(InputIterator first,InputIterator last)
            {
                while(first != last)
                {
                    push_back(*first);
                    ++first;
                 }
            }

            vector(size_t n,const T& val = T())
                :_start(new T[n])
                ,_finish(_start + n)
                ,_end_of_storage(_finish)
            {
                for(size_t i = 0;i < n;++i)
                {
                    _start[i] = val;
                }
            }

            vector(int n, const T& val = T())
                :_start(new T[n])
                ,_finish(_start + n)
                ,_end_of_storage(_finish)
            {
                for(int i = 0;i < n;++i)
                {
                    _start[i] = val;
                }
            }
            
            vector(const vector<T>& v)
                :_start(NULL)
                ,_finish(NULL)
                ,_end_of_storage(NULL)
            {
                reserve(v.capacity());
                _finish = _start + v.size();
                for(int i = 0;i < v.size();++i)
                {
                    _start[i] = v[i];
                }
            }
            
            vector<T>& operator=(vector<T> v)
            {
                swap(v);
                return *this;
            }

            void swap(vector<T>& v)
            {
                std::swap(_start,v._start);
                std::swap(_finish,v._finish);
                std::swap(_end_of_storage,v._end_of_storage);
            }
            
            ~vector()
            {
                delete[] _start;
                _start = _finish = _end_of_storage = NULL;
            }

            size_t size()
            {
                return _finish - _start;
            }

            size_t size()const 
            {
                return _finish - _start;
            }

            size_t capacity()
            {
                return _end_of_storage - _start;
            }

            size_t capacity()const 
            {
                return _end_of_storage - _start;
            }
    
            bool empty()
            {
                return _start == _finish;
            }

            bool empty()const 
            {
                return _start == _finish;
            }

            void reserve(size_t n)
            {
                if(n > capacity())
                {
                    size_t sz = size();
                    T* tmp = new T[n];
                    if(_start)
                    {
                        for(int i = 0;i < sz;++i)
                        {
                            tmp[i] = _start[i];
                        }
                        delete[] _start;
                    }
                    _start = tmp;
                    _finish = _start + sz;
                    _end_of_storage = _start + n;
                }
            }

            void resize(size_t n,const T& val = T())
            {
                if(n <= size())
                {
                    _finish = _start + n;
                }
              else 
                {
                    reserve(n);
                    iterator it = _finish ;
                    _finish = _start + n;
                    while(it != _finish)
                    {
                        *it = val;
                        it++;
                    }
                }
            }

            void push_back(const T& x)
            {
                if(_finish == _end_of_storage)
                {
                    reserve(capacity() == 0 ? 4 : capacity()*2);
                }

                *_finish = x;
                _finish++;
            }

            T& front()
            {
                return *_start;
            }

            const T& front()const 
            {
                return *_start;
            }

            T& back()
            {
                return *(_finish - 1);
            }

            const T& back()const 
            {
                return *(_finish - 1);
            }

            void pop_back()
            {
                assert(_finish > _start);
                _finish--;
            }

            iterator insert(iterator pos,const T& val )
            {
                assert(pos >= _start && pos <= _finish);
                if(_finish == _end_of_storage)
                {
                    size_t len = pos - _start;
                    reverse(capacity() == 0 ? 4 : capacity()*2);
                    pos = _start + len;
                }
                iterator end = _finish - 1;
                while(end >= pos)
                {
                    *(end+1) = *end;
                    end--;
                }
                *pos = val;
                _finish++;
                return pos;
            }

            iterator erase(iterator pos)
            {
                assert(pos >= _start && pos < _finish);
                iterator st = pos + 1;
                while(st < _finish)
                {
                    *(st - 1) = *st;
                    st++;
                }
                _finish--;

                return pos;
            }

            T& operator[](size_t pos)
            {
                assert(pos < size());
                return _start[pos];
            }

            const T& operator[](size_t pos)const 
            {
                assert(pos < size());
                return _start[pos];
            }

        private:
             iterator _start;
             iterator _finish;
             iterator _end_of_storage;
        };   

    void test_vector1()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(1);
        v1.push_back(1);
        v1.push_back(1);
        v1.push_back(1);
        
        csd::vector<int>::iterator it = v1.begin();
        while(it != v1.end())
        {
            cout << *it << " ";
            it++;
        }
    } 

    void test_vector2()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(1);
        v1.push_back(1);
        v1.push_back(1);
        v1.push_back(1);

        vector<int> v2(v1);

        csd::vector<int>::iterator it = v2.begin();
        while(it != v2.end())
        {
            cout << *it << " ";
            it++;
        }
     }  

    void test_vector3()
    {
        int arr[5] = {1,2,3,4,5};
        vector<int> v1(10,5);
         vector<int> v2(arr,arr+5);

        csd::vector<int>::iterator it = v1.begin();
        while(it != v1.end())
        {
            cout << *it << " ";
            it++;
        }

        cout << endl;

        csd::vector<int>::iterator it2 = v2.begin();
        while(it2 != v2.end())
        {
            cout << *it2 << " ";
            it2++;
        }
    }
}

int main()
{
    csd::test_vector1();
    return 0;
}
